import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-02-16
 * Time: 23:27
 */
class Solution {
//     回溯
//     转化为 有 n　个空位置
//     将 n 个数字放到这 n 个位置上
//     为了 一个位置上放过的数字不能重复
//     先将 数组排序
//     只放 同一数字中的一个, 不要再重复放了
//     因为是回溯
//     所以出现重复的情况是
//     这个位置的数字与前面一个相同
//     但前面的那个数字没有被用过
//     原因就是 当前这个位置上次用的就是前面相同的元素
//     所以再这种情况下, 该位置不能再放相同元素了
    public boolean[] visited;
    public int length;
    public List<List<Integer>> lists=new ArrayList<>();
    public List<Integer> list=new ArrayList<>();
    public void dfs(int index, int[] nums){
        if(index==this.length){
            lists.add(new ArrayList<>(list));
            return ;
        }
        for(int i=0;i<this.length;i++){
            // 如果这个数字已经被用过了, 那当然不能再用了
            // 因为是回溯
            // 所以出现重复的情况是
            // 这个位置的数字与前面一个相同
            // 但前面的那个数字没有被用过
            // 原因就是 当前这个位置上次用的就是前面相同的元素
            // 所以再这种情况下, 该位置不能再放这个元素了
            if(this.visited[i]||(i>0&&nums[i]==nums[i-1]&&!this.visited[i-1])){
                continue;
            }
            list.add(nums[i]);
            this.visited[i]=true;
            dfs(index+1, nums);
            list.remove(list.size()-1);
            this.visited[i]=false;
        }
    }
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        this.length=nums.length;
        this.visited=new boolean[this.length];
        dfs(0, nums);
        return lists;
    }
}
